package leetcode;

/**
 * http://www.leetcode.com/onlinejudge
 * 
 * Balanced Binary Trees
 * 
 * Given a binary tree, determine if it is height-balanced.
 * 
 * For this problem, a height-balanced binary tree is defined as a binary tree
 * in which the depth of the two subtrees of every node never differ by more
 * than 1.
 * 
 * @author yunzhang
 */
public class BalancedBinaryTree {
	/**
	 * Do post-order traversing over the tree, calculate the height of each node
	 * and check balance at the same time
	 * 
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		return isBalanced2(root).isBalanced;
	}

	private Ret isBalanced2(TreeNode root) {
		Ret ret;

		if (root == null) {
			ret = new Ret(true, 0);
			return ret;
		}

		Ret retL = isBalanced2(root.left);
		Ret retR = isBalanced2(root.right);

		ret = new Ret(retL.isBalanced && retR.isBalanced
				&& Math.abs(retL.height - retR.height) < 2, 1 + Math.max(
				retL.height, retR.height));

		return ret;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

class Ret {
	boolean isBalanced;
	int height;

	public Ret(boolean isBalanced, int height) {
		this.isBalanced = isBalanced;
		this.height = height;
	}
}
